﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

/// <summary>
/// Summary description for Class1
/// </summary>
public class Drzewo<T> where T : System.IComparable<T>
{
    public Drzewo() // konstruktor
    {
        tablica = null;
        rozmiar = 0;
        prawdziwy_rozmiar = 0;
    }
    public T ZwrocMin()
    {
        if (rozmiar < 1) throw new ArgumentException("Drzewo jest puste!");
        return tablica[0];
    }
    public int ZwrocRozmiar()
    {
        return prawdziwy_rozmiar;
    }
    void PushUp(int start_real_id)
    {
        //Console.WriteLine ("PushUp({0})", start_real_id);
        if (start_real_id != 1)
        {
            if (start_real_id == rozmiar)
            {//jeśli to ostatni element
                if (start_real_id % 2 == 0)
                {//jeśli to id parzyste to znaczy że nie ma brata
                    //Console.WriteLine ("31 {0} {1}", getId (getParentId (start_real_id)), getId (start_real_id));
                    //Console.WriteLine ("{0} {1}", tablica [getId (getParentId (start_real_id))], tablica [getId (start_real_id)]);

                    tablica[ZwrocId(ZwrocRodzicaId(start_real_id))] = tablica[ZwrocId(start_real_id)];
                    //Console.WriteLine ("35");
                    rozmiar--;
                    Array.Resize(ref tablica, rozmiar);
                    //Console.WriteLine ("35");
                    PushUp(ZwrocRodzicaId(start_real_id));
                    //Console.WriteLine ("37");
                }
                else
                {
                    //throw new ArgumentException ("Chyba nie powinno to nastąpić ;p");
                }
            }
            else
            {//nieparzyste => (element ma brata po lewej stronie)
                //Console.WriteLine ("#43 {0}", getId (idPrzeciwnik (start_real_id)));
                if (tablica[ZwrocId(start_real_id)].CompareTo(tablica[ZwrocId(idPrzeciwnik(start_real_id))]) < 0)
                {//kiedy wygram z przeciwnikiem
                    //Console.WriteLine ("#45");
                    tablica[ZwrocId(ZwrocRodzicaId(start_real_id))] = tablica[ZwrocId(start_real_id)];
                    PushUp(ZwrocRodzicaId(start_real_id));
                }
                else
                {
                    //Console.WriteLine("#47");
                    tablica[ZwrocId(ZwrocRodzicaId(start_real_id))] = tablica[ZwrocId(idPrzeciwnik(start_real_id))];
                    PushUp(ZwrocRodzicaId(start_real_id));
                    /*if(tablica [getId (getParentId (start_real_id))].CompareTo(tablica [getId(idPrzeciwnik(start_real_id))])!=0){
                        tablica [getId (getParentId (start_real_id))] = tablica [getId(idPrzeciwnik(start_real_id))];
                        PushUp(idPrzeciwnik(start_real_id));*/
                    //}
                }
            }
        }
    }
    public void DeleteMin()
    {
        if (prawdziwy_rozmiar == 1)
        {
            rozmiar--;
            tablica = null;
        }
        else if (prawdziwy_rozmiar > 1)
        {


            int real_element = rozmiar - prawdziwy_rozmiar + 1;
            //T[] tablica_tmp = new T[real_size-1];//tablica o wielkości ilości prawdziwych elementów minus ten który usuniemy

            int id_to_remove = FindMin();//realne id (tablicowe) elementu który ma być usunięty

            int el = 0;//id kolejnych elementów tablicy tablica_tmp
            //Console.WriteLine("Pierwszt realny el. {0} {1}", real_element, id_to_remove);
            /*for (int i = real_element; i <= size; i++)//pętla która dodaje prawdziwe elementy(z wyjątkiem usuwanego) do tymczasowej tablicy
            {
                if(id_to_remove==i)//kopiuj bez usuwanej liczby
                    continue;
                tablica_tmp[el]=tablica[getId(i)];
                //Console.WriteLine("{0} ,", tablica[getId(i)]);
                el++;
            }*/
            T ostatni_element = tablica[ZwrocId(rozmiar)];
            Array.Resize(ref tablica, ZwrocId(rozmiar));
            rozmiar--;
            // Console.WriteLine("1 {0} {1}", id_to_remove, size);
            if (ZwrocId(id_to_remove) != rozmiar)
            {
                tablica[ZwrocId(id_to_remove)] = ostatni_element;

                PushUp(id_to_remove);
            }

            PushUp(rozmiar);
        }
        prawdziwy_rozmiar--;
    }
    int FindMin()//get id of the minimal element in the table. Zwraca id idealne tzn. przy odniesieniu do tablicy należy pobrać id elementu przez getId()
    {
        int min_id = 1;//id of min object (not real table id, but imagine tablie_id + 1
        T id_to_find = tablica[0];//the minimal object has own label in 1st object in table
        for (int pointer_id = 1; pointer_id * 2 < rozmiar;)
        {//follow the labels id_to_find

            pointer_id *= 2;//ids of object, which we follow by (we're getting child)
            //Console.WriteLine("{0}", pointer_id);
            if (tablica[ZwrocId(pointer_id)].CompareTo(id_to_find) == 0)
            {
                min_id = pointer_id;
            }
            else if (tablica[ZwrocId(pointer_id + 1)].CompareTo(id_to_find) == 0)
            {//and the next element (brother)
                min_id = pointer_id + 1;
            }
            else
            {

                //Console.WriteLine("");
            }
            pointer_id = min_id;
        }
        //Console.WriteLine("ZNALEZIONE ID {0}", min_id);
        return min_id;
    }
    int ZwrocId(int i)//przekazuje id elementu w tablicy.
    {
        return i - 1;
    }
    int ZwrocRodzicaId(double i)
    {
        double t = Math.Floor(i / 2);
        return (int)t;
    }
    int idPrzeciwnik(int i)// Pobranie id przciwnika (działa na liczbach idealnych)
    {
        int p = -1;
        if (i % 2 == 0)
            p = i + 1;
        else
            p = i - 1;

        return p;
    }
    public void Show()//Wyświetlanie drzewa
    {
        double h = 0;
        int element_in_row = 0;
        for (int i = 0; i < rozmiar; i++)
        {
            if (Math.Ceiling(Math.Log(i + 2, 2)) != h)
            {
                Console.Write("\n");
                h = Math.Ceiling(Math.Log(i + 2, 2));
                element_in_row = 0;
            }
            element_in_row++;

            int space_size = rozmiar;

            if (element_in_row % 2 == 0) space_size *= 2;

            for (int space = 0; space < space_size / (Math.Pow(2, h - 1)); space++)
            {
                Console.Write(" ");
            }

            Console.Write("{0}", tablica[i].ToString());
        }

        Console.WriteLine();
    }
    void QuietInsert(T o) // dodawanie elementu do drzewa podczas "usuwania"
    {
        //if(!quiet)
        //Console.WriteLine("Dodano {0} {1} {2}", o, size, real_size);
        tablica[rozmiar] = o;
        rozmiar++;
        if (rozmiar > 1) PojedynekSzybki(rozmiar); // funkcja porównująca z rywalem, gdy mamy 1 element nie występuje pojedynek

    }
    public void Insert(T o) // dodawanie elementu do drzewa
    {
        //if(!quiet)
        //	Console.WriteLine("Dodano {0}", o);
        Array.Resize(ref tablica, rozmiar + 1);
        tablica[rozmiar] = o;
        rozmiar++;
        if (rozmiar > 1) Pojedynek(rozmiar); // funkcja porównująca z rywalem, gdy mamy 1 element nie występuje pojedynek
        prawdziwy_rozmiar++;
    }
    void insertInside(T o) // dodawanie elementu do drzewa pomijając sortowanie
    {
        Array.Resize(ref tablica, rozmiar + 1);
        tablica[rozmiar] = o;
        rozmiar++;
    }
    void insertInsideFast(T o) // dodawanie elementu do drzewa nie musząc troszczyć sie o rozmiar
    {
        tablica[rozmiar] = o;
        rozmiar++;
    }

    void copy(ref T a, ref T b) // funkcja zamieniająca ze sobą 2 obiekty
    {
        a = b;
    }
    void Pojedynek(int i) // i = rozmiar tablicy = indeks elementu +1
    {
        int przeciwnik = i / 2;

        insertInside(tablica[ZwrocId(przeciwnik)]);
        while (tablica[ZwrocId(przeciwnik)].CompareTo(tablica[ZwrocId(i)]) > 0)
        {
            copy(ref tablica[ZwrocId(przeciwnik)], ref tablica[ZwrocId(i)]);
            if (przeciwnik == 1) break;

            i = przeciwnik;
            przeciwnik = i / 2;
        }
    }
    void PojedynekSzybki(int i) // pojedynak podczas tworzenia elementów po DeleteMin
    {
        int przeciwnik = i / 2;

        insertInsideFast(tablica[ZwrocId(przeciwnik)]);

        while (tablica[ZwrocId(przeciwnik)].CompareTo(tablica[ZwrocId(i)]) > 0)
        {
            copy(ref tablica[ZwrocId(przeciwnik)], ref tablica[ZwrocId(i)]);
            if (przeciwnik == 1) break;

            i = przeciwnik;
            przeciwnik = i / 2;
        }
    }

    T[] tablica; // tablicowa struktura drzewa
    int rozmiar; // rozmiar drzewa
    int prawdziwy_rozmiar;//ilość prawdziwych elementów
}
